12. Agregarea structurilor de date
12.1 Conceptul de agregare
12.2 Agregare pe orizontala
12.3 Agregare pe verticala
12.4 Expresiile de referire ale structurilor agregate
12.5 Efectele agregarii
12.6 Exemplificare proces de agregare structuri
back data structures curricula
12.1 Conceptul de agregare
Presupune existenta structurilor de date S1, S2, S3, ....., Si, ........, Sj, .....Sn.
Se defineste operatia de compunere * de structuri de date prin
Si * Sj, necomutativa, operatie numita AGREGARE care conduce la obtinerea unei noi structuri Sij, de date, cu proprietati noi, cu un nivel de complexitate mult mai ridicat.
Daca se considera structurile:
vector
matrice
lista simpla
lista dubla
arbore binar
graf
stiva
- se obtin agregari pe orizontala de forma:
Si * Si
- structuri prin agregari pe verticala
Si * Si
....................
....................
....................
....................
....................
....................
....................
....................
revenire
12.2 Agregare pe orizontala
Presupune utilizarea structurilor de date de acelasi tip.
Structurile agregate pe orizontala sunt:
vector de vector
matrice de matrice
liste de liste
arbori de arbori
graf de graf.
Daca mai multe elemente de acelasi tip se concateneaza, rezulta un vector.
Cprin agregarea de vectori de vectori rezulta matricea.
Un element din vector se refera prin nume[expresie].
Un element dintr-un vector de vectori se refera prin
nume[expresie_1][expresie_2]
Daca articolul contine campurile C1 de tip1, C2 de tip2, C3 de tip3,...,
Cn de tipn, vetorul de articole apare ca o concatenare de articole.
Omogenitatea este data de faptul ca toate componentele vectorului au acelasi sablon.
....................
....................
....................
....................
....................
....................
....................
....................
revenire
12.3 Agregare pe verticala
Agregarea pe verticala presupune definirea mai multor tipuri de structuri in care unele campuri sunt folosite pentru a referi alte structuri.
Agregari pe verticala sunt de exemplu:
vector de matrice
vector de liste
vector de articole
vector arbori
vector de liste
matrice de vector
lista de vectori
liste de arbori
lista dubla de vectori
liste duble de arbori
arbore binar de vectori
arbori binari de liste
graf de vectori
stiva de articole
striva de matrice
Numarul combinatiilor este foarte mare.
Pentru agregarea listelor pe doua nibeluri se definesc:
- o lista de baza pe primul nivel
- mai multe liste derivate, pe al doilea nivel.
Lista de listeare ca elemente in lista de baza definiri de forma:
struct lista_baza{
struct lista_deriv *pderiv;
struct lista_baza *next;}
struct lista_deriv {
int info;
struct lista_deriv *next_deriv;}
In cazul articolelor de vectori se lucreaza cu o reuniune de vectori de diferite tipuri, intrucat prin natura lucrurilor, campurile ce formeaza aricolul sunt de tipuri diferite.
Trecerea la agregarea dintre vectori si liste presupune obtinerea de vectori de liste vectorul avand ca elemente pointeri spre elementele unor liste generate dinamic dupa acelasi sablon.
Articolul de liste permite regruparea de liste cu sabloane diferite prin intermediul pointerilor care sunt campuri dintr-un articol, definit prin:
struct articol {
struct lista_1 * pcplist1;
struct lista_2 * pcplist2;
struct lista_3 * pcplist3;
struct lista_4 * pcplist4;
.......................
struct lista_n * pcplistn;
}
unde:,br>
struct lista_i {
tip_i1 camp_i1;
tip_i2 camp_i2;
tip_i3 camp_i3;
tip_i4 camp_i4;
..............
tip_in camp_in;
}
i=1,2,...,n
Daca trebuie efectuate prelucrari pe structuri omogene cu vectori cu numar oarecare de componente se definesc liste de vectori. Fiecare element al listei permite referirea unor elemente din vector.
Este necesar ca elementul listei sa aiba o informatie ce contine numarul de elemente ale vectorului al carui pointer are alocare dinamica de memorie pentru elementele vectorului.
Arborii oarecare permit stocarea pointerilor spre descendenti fie folosind vectori de pointeri alocati dinamic sau incorporati in nodul parinte, ceea ce conduce la utilizare mai putin eficienta.
Pentru arborele oarecare cu nodurile A, B, C, D, E, F, G, H, I, J, gradul de utilizare GU2 este date de relatia, iar valorile calculate arata diferenta fata de situatia in care numarul de elemente in vectorul de pointeri este fix, iar gradul de utilizare GU1 este dat de relatia unde o contributie nefavorabila au au nodurile cu putini descendenti.
....................
....................
....................
....................
....................
....................
....................
....................
revenire
12.4 Expresiile de referire ale structurilor agregate
....................
....................
....................
....................
....................
....................
....................
....................
revenire
12.5 Efectele agregarii
....................
....................
....................
....................
....................
....................
....................
....................
revenire
12.6 Exemplificare proces de agregare structuri
Pentru agregarea structurilor de date se exemplifica definirea documentului factura
Se defineste o structura pentru identificarea furnizorilor si beneficiarilor.
Se defineste un articol pentru identificarea produsului care face obiectul tranzactiei(cod, denumire, unitate de masura, cantitate, pret unitar, valoare, TVA.
Se defineste o structura pentru identificarea celor care intocmesc documentul, respectiv, care asigura transportul si receptioneaza produsele.
Structura de date agregata opereaza cu vectori de structura.
pentru orice factura care se elibereaza, se construieste un element intr-o lista simpla.
La sfarsitul zilei se stocheaza informatia utila din lista simpla (facturile) intr-un fisier.
....................
....................
....................
....................
....................
....................
....................
....................
revenire
